package io.gitee.wiqer.medium;

import java.util.*;
import java.util.concurrent.ConcurrentSkipListMap;

/**
 * 描述
 * 给定一个字符串数组，再给定整数 k ，请返回出现次数前k名的字符串和对应的次数。
 * 返回的答案应该按字符串出现频率由高到低排序。如果不同的字符串有相同出现频率，按字典序排序。
 * 对于两个字符串，大小关系取决于两个字符串从左到右第一个不同字符的 ASCII 值的大小关系。
 * 比如"ah1x"小于"ahb"，"231"<”32“
 * 字符仅包含数字和字母
 *
 * 数据范围：字符串数满足 0 \le n \le 1000000≤n≤100000，每个字符串长度 0 \le n \le 100≤n≤10，0 \le k \le 25000≤k≤2500
 * 要求：空间复杂度 O(n)O(n)，时间复杂度O(n \log k)O(nlogk)
 */
public class SolutionNC97_TopKStrings {
    /**
     *
     * 搞半天，没有灵活运用list排序和map.get()
     * @param strings
     * @param k
     * @return
     */
    public static String[][] topKstrings(String[] strings, int k) {
        // write code here
        SortedMap<String, Integer> map = new TreeMap<>();
        for (String str : strings) {
            map.put(str, map.getOrDefault(str, 0) + 1);
        }
        List<String> rec = new ArrayList<String>();
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            rec.add(entry.getKey());
        }
        Collections.sort(rec, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return map.get(o1) == map.get(o2) ? o1.compareTo(o2) : map.get(o2) - map.get(o1);
            }
        });
        int i = 0;
        String[][] topk = new String[k][2];
        for (String key : rec) {
            if (i >= k) {
                break;
            }
            topk[i][0] = key;
            topk[i][1] = String.valueOf(map.get(key));
            i++;
        }

        return topk;
    }
    public static String[][] topKstrings_ConcurrentSkipListMap(String[] strings, int k) {
        // write code here
        ConcurrentSkipListMap<String, Integer> map = new ConcurrentSkipListMap<>();
        for (String str : strings) {
            map.put(str, map.getOrDefault(str, 0) + 1);
        }
        List<String> rec = new ArrayList<String>();
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            rec.add(entry.getKey());
        }
        rec.sort(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return map.get(o1).equals(map.get(o2)) ? o1.compareTo(o2) : map.get(o2) - map.get(o1);
            }
        });
        int i = 0;
        String[][] topK = new String[k][2];
        for (String key : rec) {
            if (i >= k) {
                break;
            }
            topK[i][0] = key;
            topK[i][1] = String.valueOf(map.get(key));
            i++;
        }

        return topK;
    }
}
